﻿#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

/**
 * 找到一个数字左边和右边比它本身小且离它最近的数字
 * @param table 记录每一个数字的离它最近的数字，第一个元素代表左边，第二个元素代表右边
 */
static void getAroundMinNumbers(const int* numbers, size_t size, unordered_map<int, int*>& table)
{
    // 单调栈，递增栈
    stack<int> iStack;
    for (int i = 0; i < size; i++)
    {
        int cur = numbers[i];
        if (iStack.empty())
        {
            iStack.push(cur);
        }
        else
        {
            while (!iStack.empty())
            {
                int top = iStack.top();
                if (top < cur)
                {
                    break;
                }
                else
                {
                    // 结算弹出的元素
                    int left = -1;
                    iStack.pop();
                    if (!iStack.empty())
                    {
                        left = iStack.top();
                    }

                    int right = cur;
                    int* twoNumbers = (int*)malloc(2 * sizeof(int));
                    twoNumbers[0] = left;
                    twoNumbers[1] = right;
                    table.insert({ top, twoNumbers });
                }
            }

            iStack.push(cur);
        }
    }

    while (!iStack.empty())
    {
        int cur = iStack.top();
        iStack.pop();
        int left = -1;
        if (!iStack.empty())
        {
            left = iStack.top();
        }

        int right = -1;
        int* twoNumbers = (int*)malloc(2 * sizeof(int));
        twoNumbers[0] = left;
        twoNumbers[1] = right;
        table.insert({ cur, twoNumbers });
    }
}

/**
 * 在数组中找到一个数，左边和右边比这个数小，且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息，能不能整体代价达到O(N)?
 * 需要使用单调栈结构。
 *
 * 假设数组中没有重复的值。
 * 数组:[3,5,2,7,6], 使用一个栈，从栈底到栈顶，数字由小到大排序。
 *
 * (1) 栈压入3，
 * ——————
 * | 3 ←
 * ------
 *
 * (2) 5比3大，故压入栈
 * ——————
 * | 3 5←
 * ------
 *
 * (3) 2比5小，先弹出5，并结算5，5左边比它小的是栈底的3，右边比它小的是2，结算之后，将5抛弃掉；
 * 2比3小，弹出3，并结算3, 3左边已经是栈底了，没有数字了，故左边无比它小的数，右边比它小的是2，结算之后，将3抛弃掉
 * ——————
 * | 3    →5   ←2
 * ------
 *
 * ——————
 * |      →3   ←2
 * ------
 *
 * ——————
 * | 2
 * ------
 *
 * (4) 7比2大，压入栈
 * ——————
 * | 2 7 ←
 * ------
 *
 * (5) 6比7小，先弹出7，并结算7, 7左边比它小的是栈底的2，右边比它小的是6，结算之后，将7抛弃掉；
 * 6比2大，压入栈
 * ——————
 * | 2    →7   ←6
 * ------
 *
 * ——————
 * | 2 6
 * ------
 *
 * (6) 没有新数字了，故开始结算栈内的元素，先弹出6,6的左边是栈底的2，右边没有，抛弃6；由于目前栈空了，故2左边无比它小的数字，而且也没有要加入的数字了，故右边也没有比它小的数字了。
 * ——————
 * | 2    →6
 * ------
 *
 * ——————
 * |      →2
 * ------
 */
int main_AroundNumberLowerThanSelf()
{
    int numbers[] = { 4,5,3,7,6,8,9,10,13,12 };
    size_t size = sizeof(numbers) / sizeof(int);
    unordered_map<int, int*> table;
    getAroundMinNumbers(numbers, size, table);

    for (auto iPair = table.begin(); iPair != table.end(); ++iPair)
    {
        int target = iPair->first;
        int* twoNumbers = iPair->second;
        printf("%d-> %d, %d\n", target, twoNumbers[0], twoNumbers[1]);
    }

    return 0;
}